/*
https://leetcode.cn/problems/guess-number-higher-or-lower-ii/description/
375.猜数字大小2
方钊堉 2024.10.19
区间dp
*/
class Solution {
public:
    int f[210][210];

// 计算在最坏情况下确保猜出正确数字所需的最小金额
int getMoneyAmount(int n) {
    // 初始化动态规划数组
    for (int length = 2; length <= n; length++) { // 枚举所有可能的区间长度
        for (int start = 1; start + length - 1 <= n; start++) { // 枚举所有可能的起始位置
            int end = start + length - 1; // 计算区间的结束位置
            f[start][end] = 0x3f3f3f3f; // 初始化当前区间的最小成本为一个很大的值

            // 枚举区间内的所有可能的猜测值
            for (int guess = start; guess <= end; guess++) {
                // 更新当前区间的最小成本
                // max(f[start][guess-1], f[guess+1][end]) 表示在最坏情况下，无论目标数字在左侧还是右侧，都需要支付的最大金额
                // 加上当前猜测值 guess 表示本次猜测的成本
                f[start][end] = min(f[start][end], max(f[start][guess-1], f[guess+1][end]) + guess);
            }
        }
    }
    return f[1][n]; // 返回整个区间 [1, n] 的最小成本
}
};